# T1 青蛙跳台阶
# T2 快排
# 口述反转链表思路

from typing import List


def partition(nums: List, low, high):
    i = low - 1
    pivot = nums[high]

    for j in range(low, high):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i+1], nums[high] = nums[high], nums[i+1]
    return i + 1


def quick_sort(nums: List, low, high):
    if len(nums) < 2:
        return
    if low < high:
        pi = partition(nums, low, high)
        quick_sort(nums, low, pi-1)
        quick_sort(nums, pi+1, high)


if __name__ == '__main__':
    nums = [4,3,9,7,2,0]
    quick_sort(nums, 0, len(nums)-1)
    print(nums)
